//
// Created by Administrator on 2021/5/31.
//
#include <iostream>

using namespace std;

class Solution {
public:
    bool isPowerOfFour(int n) {
        // 先是2的幂
        if (n < 0 or (n & (n - 1)) != 0) return false;
        // 二进制应该有奇数位
        int bitLen = 0;
        while (n) {
            n >>= 1;
            ++bitLen;
        }
        return bitLen % 2;
        //一个在偶数位为1，奇数位为0的mask
//        return n > 0 && (n & (n - 1)) == 0 && (n & 0xaaaaaaaa) == 0;
        // 对3取余，一定剩下1
//        return n > 0 && (n & (n - 1)) == 0 && n % 3 == 1;
    }
};


int main() {
    Solution sol;
    cout << sol.isPowerOfFour(2) << endl;
    cout << sol.isPowerOfFour(4) << endl;
    cout << sol.isPowerOfFour(1) << endl;
    cout << sol.isPowerOfFour(8) << endl;
    cout << sol.isPowerOfFour(16) << endl;
    return 0;
}